The Shuffler's Dilemma

Anyone can shuffle cards by hand; getting a computer to do it takes talent. Should the computer imitate a human shuffler or behave like a machine? How can the results of a shuffle be evaluated? This case study describes programs implementing several different shuffling algorithms and compares the results.

Problem Statement

Write a function called Shuffle to rearrange a (simulated) deck of cards. Create a function that will rearrange the cards such that any ordering of the cards is equally probable. Shuffle will be used in programs that simulate the play of card games and that compare different shuffling algorithms.

The function will have the following header:

def Shuffle(deck):

It will assume the following definitions:

DECKSIZE = 52
CardType = some type
DeckType = [0 for _ in range(DECKSIZE)]

Shuffle will rearrange the contents of deck, returning its "cards" in a different order. Each element contained in deck when Shuffle is entered will also be somewhere in deck - possibly in a different position when Shuffle returns. The function may make no assumptions about how CardType is defined, except to assume that assignments are possible between two CardType values.

Analysis

10.1 Suppose that a "deck" has only three cards. List all the ways the cards can be ordered.

Analysis

10.2 How many possible ways can N "cards" be arranged in a deck?

Analysis

10.3 How many possible rearrangements of an N-card deck change the position of all N cards?

Application

10.4 Define a type that represents all the characteristics of an actual playing card used in a game such as gin rummy.

Preparation

The reader is expected to be familiar with arrays and dictionary.

Understanding the Problem

What does "shuffling" a simulated deck mean?

This problem involves simulating an activity that is usually done by hand. It makes sense to pinpoint the similarities and differences between shuffling by hand and "shuffling" in a program. Shuffling a deck of actual cards means mixing them up. "Shuffling" a simulated deck means the same thing. Here's an example that uses a deck of four "cards," each being a letter.

Original deck contents

Possible result of "shuffling"

Another possible result of "shuffling"

Note that the result of shuffling need not move all the cards; the first shuffle above left card 'B' in the second position in the deck.

Stop & Consider

Might shuffling leave a deck unchanged? Why or why not?

Stop & Help

How many possible ways can four cards be arranged in a deck?

Stop & Help

How many possible rearrangements of a four-card deck change the position of all four cards?

What is a successful shuffle?

The problem statement asks for a shuffle in which any of the possible rearrangements of the deck should be equally probable. Thus, the problem statement requires that the shuffling be "unpredictable." An example of a predictable shuffling routine would be one that always leaves the second card in the second position.

Stop & Help

Why might shuffling by hand yield predictable results?

Why use the given declarations?

The problem statement requires that the function use specific declarations. These appear to be chosen so that the function will be modular and work with many different programs.

The use of the constant DECKSIZE to specify the size of the deck allows the size to be changed easily. Using a constant also makes it easier to test Shuffle on smaller problems. The same approach was used in Space Text.

The problem statement specifies that the Shuffle code must not depend on the characteristics of a CardType. Thus it should work as well if CardType were char (as in the above example) as if it were integer, or a more complicated type.

Analysis

10.5 How might the code of the Shuffle function depend on the characteristics of a CardType?

Application

10.6 Why might Shuffle be used for decks of size other than 52?

Reflection

10.7 What parts of hand shuffling would be difficult to simulate?

A "Perfect Shuffle"

How do people shuffle a deck of cards?

One possible solution simulates how people shuffle cards. Most people split the deck in half and then interleave the cards, as shown in the diagram below.

Applied to a deck of four cards (letters for the purposes of this example), this function works as follows:

What is a "perfect shuffle"?

If the deck is split precisely in half, and the halves are precisely interleaved, the function is called a "perfect shuffle." We decide to implement a version of Shuffle using the perfect shuffle function first, on the assumption that this is close to the algorithm that many people use.

Stop & Predict

What are the limitations of the perfect shuffle solution?

As in previous case studies, it helps to make a table of the desired rearrangement. The function illustrated above provides a table for shuffling a four - card deck. For a 52 - card deck:

Stop & Help

Suppose the deck consists of the integers 1 through 52, arranged in increasing order. How are the integers ordered after a perfect shuffle?

What implementation does the table suggest?

The table suggests a way to implement the shuffle. We can use two decks, the deck provided as a parameter and another deck - we'll call it shuffledDeck - used as a local variable. We can keep track of a position in each deck, oldPosition in deck and shuffledPosition in shuffledDeck. The shuffle then can consist of loops that copy deck[oldPosition] into shuffledDeck[shuffledPosition], then update old Position and shuffled Position, in each iteration. The shuffle finishes by copying shuffled Deck back into deck.

Stop & Help

The code to copy shuffledDeck into deck is an example of a template used in previous case studies. Which template is it, and where was it used?

For the first half of the deck, oldPosition starts at 0 and goes up by 1 at each step, and shuffledPosition starts at 0 and goes up by 2 at each step. The second half of the deck is handled similarly, except for different starting values. We will call this approach PerfectShuffle and implement it. Assuming for simplicity that the deck has an even number of cards, we arrive at the following code:

def PerfectShuffle(deck):
oldPosition = 0
shuffledPosition = 0
shuffledDeck = DeckType.copy()
while oldPosition < DECKSIZE // 2:
shuffledDeck [shuffledPosition] =
deck [oldPosition]
oldPosition = oldPosition + 1
shuffledPosition = shuffledPosition + 2
shuffledPosition = 1
while oldPosition < DECKSIZE:
shuffledDeck [shuffledPosition] =
deck [oldPosition]
oldPosition = oldPosition + 1
shuffledPosition = shuffledPosition + 2
for oldPosition in range(DECKSIZE):
deck [oldPosition] = shuffledDeck [oldPosition]

Stop & Help

Should old Position be reinitialized for the second loop in PerfectShuffle. Why or why not?

Does the function satisfy the conditions of the problem statement?

The perfect shuffle function meets the problem specifications in that (a) it uses the given declarations, and (b) it makes no assumptions about CardType values other than that one CardType value can be assigned to a variable of type CardType.

Stop & Predict

How effectively does PerfectShuffle shuffle the cards?

How should PerfectShuffle be tested?

The PerfectShuffle function and a program to test it appear in the Python Code section. To test for predictability we print the result of repeated calls to PerfectShuffle. At each iteration the result of the previous shuffle is shuffled again. We hope that any patterns in the shuffling will show up in the resulting output.

Stop & Help

Test PerfectShuffle using the program in the Python Code section with DECKSIZE set to 6.

What is the result of the test?

The program produces a very predictable shuffle. Here is a table representing the shuffling process for a deck of four cards:

Perhaps it works better with a bigger deck? Trying DECKSIZE = 8 results in equally disappointing behavior:

Deck:
A E B F C G D H

Deck:
A C E G B D F H

Deck:
A B C D E F G H

Deck:
A E B F C G D H

Deck:
A C E G B D F H

Deck:
A B C D E F G H

and so on. We conclude that a perfect shuffle is too predictable to satisfy the problem specifications, so we go back to thinking up alternative solutions.

Modification, Reflection

10.8 Code the while loops in PerfectShuffle as for loops. Which version do you prefer? Explain.

Reflection

10.9 Why does the use of shuffledDeck result in simpler code than would the use of only one deck variable?

Modification

10.10 Rewrite PerfectShuffle to use only one position variable. Compute the value of a card's position in the shuffled deck from the value of oldPosition, its value in the unshuffled deck.

Modification

10.11 Rather than compute the value of a card's position in the shuffled deck from the value of oldPosifion as in question 10.10, one may instead compute the card's position in the unshuffled deck from shuffledPosition. Provide the missing expression for the loop below to rearrange the deck using a perfect shuffle. Hint: use % and //.

for shuffledPosition in range(DECKSIZE):
shuffledDeck [shuffledPosition]
= deck[__________]

Analysis

10.12 How many shuffles are needed for PerfectShuffle to return a 52-card deck to its original arrangement? (This is the basis of a magician's trick, in which the magician carefully shuffles the cards many times, apparently mixing them up thoroughly, yet is able to predict the order of cards in the deck.)

Analysis

10.13 Which statements in the program in the Python Code section depend on the characteristics of a CardType?

Analysis

10.14 If 52 were used throughout the code instead of the constant DECKSIZE, how many changes would be necessary to test the program on a deck of size 4?

Debugging

10.15 What would happen if the main program in the Python Code section reinitialized the deck inside the for loop?

Analysis

10.16 What does PerfectShuffle do if DECKSIZE is odd?

Modification

10.17 Fix PerfectShuffle to shuffle a deck containing an odd number of cards correctly.

Analysis

10.18 Suppose we interleaved the cards in a different order, as shown in the diagram below. Would this process yield a shuffle function that's better than PerfectShuffle?

Shuffling With a Random Number Generator

How can the shuffle function be made less predictable?

To get an unpredictable shuffle we need a random number generator. This is a function that, when called repeatedly, returns a sequence of numbers that appear random. (Since the numbers are produced by program code, they aren't really random; because of this, programmers sometimes call the function a "pseudorandom" number generator.) Almost all Python environments provide some sort of random number generator, either a function that returns a random integer or a function that returns a random real value between 0 and 1. In the remainder of the solution to this problem, we will assume that a function named Randomint, which takes no arguments, is available that returns a random integer value.

Stop & Help

Find out which random number generator is available on your Python system.

Stop & Help

Write a test program that calls the random number generator 100 times and prints the values it returns. Do they look "random"?

Stop & Help

How might the RandomInt function be used to shuffle the cards? List all your ideas.

How can the Randomint function be used in a card-shuffling function?

We can use Randomint to simulate the choice of a random card from the deck. To determine how choice of a random card might be incorporated into a shuffling function, it helps to consider how this would work for hand shuffling. Some possibilities:

Shuffling by exchanging: A person might repeatedly choose two cards at random and exchange them.

Shuffling by selection: A person might randomly choose a card and add it to the shuffled deck until there are no more cards to be chosen.

Shuffling by insertion: A person might repeatedly take the top card in the deck and insert it next to a randomly chosen card.

We will pursue the first two of these approaches and leave the last for consideration in a study question.

Application

10.19 Suppose that a Python system provides a function RandomReal that returns a random real value that's greater than 0 and at most 1. Implement Randomint in terms of RandomReal.

Application

10.20 Use Randomint in a program to simulate repeated throws of two six sided dice.

Analysis

10.21 Randomint differs from other functions in one significant way. What is it?

Application

10.22 List other uses for a random number generator.

Reflection

10.23 Describe how prior case study solutions might be reused to implement these alternatives.

Shuffling by Random Exchanges

How can random exchanges of cards be done to shuffle the deck?

A descriptive name for the solution based on random exchanges is ExchangeShuffle. In pseudocode, the solution is as follows:

while not done:
choose two random positions in deck
exchange the cards at those positions

The pseudocode doesn't specify a way to stop the loop. The body of the loop, however, isn't hard to design. Exchanging elements of an array is easy, and choosing two random positions in deck will involve calling Randomint and using its result.

Stop & Predict

What will determine the ideal number of exchanges?

How can a random position in the deck be found?

A random position in deck is merely a random integer between 1 and DECKSIZE, inclusive. Randint returns a random integer. Since this expression will be used more than once (and will probably be useful in alternative solutions to the problem), we code it as a function

def RandomDeckPos():
import random
RandomDeckPos = random.randint(0, DECKSIZE-1)
return RandomDeckPos

The pseudocode for ExchangeShuffle may then be refined to

while not done:
pos1 = RandomDeckPos
pos2 = RandomDeckPos
exchange deck[pos1] with deck[pos2]

How many exchanges are necessary to shuffle the deck adequately?

To determine how many exchanges are necessary, we try some possibilities. We examine as small a deck as necessary to give us the information we need; even a deck of size 4 gives a large number of possibilities, so we start with a deck of size 3. We create a diagram to determine all the possibilities.

Stop & Predict

Suppose two exchanges of cards are made-two randomly chosen cards are exchanged, and then two other randomly chosen cards are exchanged. Which pairs of exchanges return a "shuffled" deck identical to the original?

Figure 10.1 indicates the possible deck orderings that result from one and two exchanges. There are nine possible ways to make the first exchange; for each of those, there are nine possible ways to make the second exchange. An exchange of, say, the first card with the second card is represented by "1<->2"in the figure, an exchange of the second card with the third card is represented by 2<->3 and so on. Potentially, RandomDeck Pos might select the same card on two successive calls. The possibilities for this are "1<->1,""2<->2" and "3<->3." All three possibilities merely result in the corresponding card being "exchanged" with itself.

Figure 10.1 shows that the various rearrangements of the deck show up with the frequencies displayed in Table 10.2.

Stop & Help

List the 12 ways that the ordering BAC can be produced by two exchanges.

Stop & Help

Verify the accuracy of the below Table.

Stop & Help

Determine the frequency of the arrangements of the three-card deck that results from three exchanges.

Stop & Predict

Are the shuffled versions of the deck equally probable?

Stop & Predict

Does ExchangeShuffle meet the problem specifications?

It appears that some arrangements of cards (in particular, the original arrangement) occur much more frequently than others. We thus reject shuffling by exchanges.

Application

10.24 Write a program to verify the data in Figure 10.1.

Application

10.25 Write a program to produce the number of ways to arrive at each ordering of four cards using two exchanges.

Analysis

10.26 Is shuffling by exchanges any better if exchanges of a card with itself are prohibited? Explain.

Modification

10.27 Test your answer to question 10.26 by modifying the ExchangeShuffle function so that it keeps generating random positions until it finds two positions that are different. (This avoids exchanging a card with itself.)

Shuffling by Selection

How can random selection help shuffle the deck?

A descriptive name for a solution based on random selection of a card is SelectionShuffle. The approach is to choose a random card and add it to the shuffled deck until there are no more cards to be chosen. We note that the same card may be chosen twice. To avoid this problem we can keep track of the cards that have already been chosen and add a card to the shuffled deck only if it's not there already. In pseudocode:

set the number of cards already chosen to 0
while number of cards already chosen < DECKSIZE:
choose a random card
compare it with cards already chosen
if it doesn't match:
add it to the shuffled deck
add 1 to the number of cards already chosen

Stop & Predict

Which array templates are used to produce the code?

We use the deck and shuffledDeck variables to refine the pseudocode into Python.

def SelectionShuffle(deck):
k = 0
numChosen = 0
shuffledDeck = DeckType.copy()
while numChosen < DECKSIZE:
k = RandomDeckPos()
if not Search(deck[k], shuffledDeck, numChosen):
shuffledDeck [numChosen] = deck[k]
numChosen = numChosen + 1

The loop body is similar to code used to fill an array. The Search function is a variation of code used in earlier case studies.

Stop & Help

Why not use a for loop in Selection Shuffle rather than a while loop?

How well does this function work?

The code for SelectionShuffle and the subprograms it calls appears in the Python Code section. The same main program used to test PerfectShuffle can be used with SelectionShuffle. As before, we test it on decks of size 4 and size 52. It seems to work fine.

Stop & Help

Test SelectionShuffle on your system. Compare the time it takes to shuffle a deck of 52 cards to the time PerfectShuffle takes.

What flaws does SelectionShuffle have?

One unsettling aspect of SelectionShuffle is that the while loop is not absolutely guaranteed to terminate.

Stop & Help

Explain why the while loop could take a long time to terminate.

Admittedly the loop is unlikely to go on forever. Finishing up the shuffle of a deck of 52 cards, though, will require quite a few calls to RandomDeckPos to choose the cards that have not yet been included in the shuffle.

Stop & Help

Suppose the loop of SelectionShuffle has progressed to the point where numChosen is equal to DECKSIZE-1. Assuming that RandomDeckPos is equally likely to return any of the possible deck positions, what is the probability that one more execution of the loop body will finish the shuffle?

How can SelectionShuffle be improved?

The algorithm of SelectionShuffle does not accurately reflect what a person using the selection approach would do. A person would pick a random card, add it to a pile, pick a random card from those that remain, add it to the pile, and so on. Thus the first random card would be chosen from a deck of DECKSIZE cards, the next from a deck of DECKSIZE-1 cards, the third from a deck of DECKSlZE-2 cards, and so on. A descriptive name for this solution is EfficientSelectionShuffle. In pseudocode:

set the number of cards already chosen to 0
while number of cards already chosen < DECKSIZE:
choose a random card from those that remain in deck
add it to the shuffled deck
remove it from deck

Stop & Help

Are any changes to SelectionShuffle needed to add cards to the shuffled deck in EfficientSelectionShuffle?

How can the deck be adjusted when cards are removed?

We need to reduce the cards in deck when a card is removed so that choosing a random card from those that remain can be done efficiently. We could modify RandomDeckPos to return a card from a deck with a variable number of cards. The size of the deck can be supplied as a parameter. Thus the modified RandomDeckPos will be called with an argument of first DECKSIZE, then DECKSIZE-1, and so on.

Removing a card from the deck to make a smaller deck requires filling the place where the card is removed. One option is to shift all cards that follow it back one place in the deck as was done to compress a Roman numeral in Is It Legal? However, this involves much more work than is necessary. There is no need to preserve the order of the cards that remain. (We're shuffling them, after all!) We can fill the gap that results from removing a card merely by moving the last card in the deck to replace it.

Stop & Consider

How is this related to the ExchangeShuffle solution?

These refinements result in the following code for EfficientSelectionShuffle. The program appears in the Python Code section.

for shuffledPos in range(DECKSIZE):
k = RandomDeckPos (DECKSIZE
- shuffledPos)
shuffledDeck [shuffledPos] = deck[k]
deck[k] = deck [DECKSIZE
-1 - shuffledPos]

EfficientSelectionShuffle satisfies the constraints on use of CardType. It seems to shuffle the cards well, though there may be patterns in the shuffling that we don't notice. For a small deck of cards, Efficient SelectionShuffle does not seem much faster than SelectionShuffle, but efficiency increases when there are many cards. This version seems to meet all the requirements of the problem and is renamed Shuffle to conform to the conditions of the problem statement.

Modification

10.28 Instead of using a search routine to determine if a card has already been included in the shuffled deck, use a Python set positionsChosen to contain the positions already chosen, and replace the if test in SelectionShuffle by the code

if not (k in positionsChosen):

Analysis

10.29 SelectionShuffle as written does not satisfy the specifications in the problem statement. Why not?

Testing

10.30 Add code to SelectionShuffle to count the number of times RandomDeckPos is called for any particular shuffle. Are you surprised by the result? Explain.

Testing

10.31 Run the program for Efficient SelectionShuffle. Is it noticeably faster than the program for SelectionShuffle for shuffling a 52-card deck? How about a 104-card deck?

Analysis

10.32 Why can a for loop be used in EfficientSelectionShuffle but was not appropriate for SelectionShuffle?

Analysis

10.33 After copying deck[DECKSIZE - shuffledPos+1] into deck[k], the code for EfficientSelectionShuffle doesn't store anything into deck[DECKSIZE - shuffledPos+1]. Should it? Why or why not?

Outline of Design and Development Questions

These questions summarize the main points of the commentary.

Understanding the Problem
What does "shuffling" a simulated deck mean?
What is a successful shuffle?
Why use the given declarations?

A "Perfect Shuffle"
How do people shuffle a deck of cards?
What is a "perfect shuffle"?
What implementation does the table suggest?
Does the function satisfy the conditions of the problem statement?
How should PerfectShuffle be tested?
What is the result of the test?

Shuffling With a Random Number Generator
How can the shuffle function be made less predictable?
How can the Randomint function be used in a card-shuffling function?

Shuffling by Random Exchanges
How can random exchanges of cards be done to shuffle the deck?
How can a random position in the deck be found?
How many exchanges are necessary to shuffle the deck adequately?

Shuffling by Selection
How can random selection help shuffle the deck?
How well does this function work?
What flaws does SelectionShuffle have?
How can SelectionShuffle be improved?
How can the deck be adjusted when cards are removed?

Programmers' Summary

This case study considers the problem of shuffling a computerized deck of cards. The shuffling function developed as a solution works with an array of any kind of "card," and thus should be a useful tool for a variety of applications.

Three alternative approaches are considered: a "perfect shuffle," based on interleaving the cards; repeated exchanges of randomly chosen cards; and repeated selection of randomly chosen cards. The latter two approaches use a random number generator, a function provided in Python environments to produce a sequence of random-looking values. The random selection approach is most successful at producing all possible card orderings with equal probability.

Different kinds of analysis are applied to the various methods. We implement the perfect shuffle and try it on small decks, noting that repeated shuffles lead quickly to the original arrangement! We analyze the random exchange method by hand and find that one arrangement (the original) consistently pops up more often than the others. After coding a version of selection shuffling, we analyze the code and find a way to improve its efficiency.

There are several uses of the Recycling principle, as array templates are applied to fill, copy, and search the deck array. The Multiple Representations principle suggests the use of a table to keep track of card rearrangement in the perfect shuffle and the use of a tree diagram to keep track of the possibilities for rearrangement via random exchanges.

Making Sense of The Shuffler's Dilemma

Application

10.34 Sorting an array (putting its elements in order) may be viewed as "unshuffling" the array. Devise sorting algorithms based on each of the approaches discussed for sorting.

Application

10.35 Design a shuffling function based on insertion, in which the top card of the deck is inserted next to a randomly chosen card.

Reflection

10.36 Which shuffling approach most closely resembles the "52-pickup" technique, where a deck of cards is flung into the air and then collected off the floor?

Modification

10.37 Modify all the Shuffle functions to use a deck represented as a dictionary in which the number of cards is stored along with the cards themselves.

Modification

10.38 Modify EfficientSelectionShuffle to use only the deck array and not the shuffledDeck array to do the shuffling. Thus only elements of deck will be exchanged to do the shuffling.

Application

10.39 Write a program to play Clock Solitaire. The player deals the cards face down into thirteen piles of four cards each and turns over the top card of the thirteenth pile. The player then puts the turned-over card face up under the pile corresponding to its rank-ace goes to the first pile, 2 to the second, and so on-and turns over the top card of that pile. The game is won if all other cards get turned over before the fourth king.

Analysis

10.40 Compare the code in EfficientSelectionShuffle to Python code that fills one array with the elements of another in reverse order. What are the similarities? What are the differences?

Reflection

10.41 Explain why considering several alternatives helps programmers come up with a better solution than considering just one.

Reflection

10.42 Analysis of small cases by hand allowed us to reject the approach of shuffling by exchanges. In what situations have you written an incorrect program that could have been avoided had you analyzed the situation by hand before coding?

Reflection

10.43 Why was it a good idea to start with PerfectShuffle even though this approach did not meet all the specifications of the problem?

Analysis

10.44 Give advice to a card player who asks if it matters how many times the cards are shuffled when the shuffling is done by hand. Would the same arguments apply to a selection shuffle?

Reflection

10.45 In what ways does the use of a random number generator make a program more difficult to test? How did we compensate for this in The Shuffler's Dilemma?

Application

10.46 Write a function that, given two integer arguments numCards and numExchanges, prints the number of times each arrangement of a deck of numCards cards results from numExchanges exchanges. Your function could be used to generate the data in Table 10.2. Hint:Use recursion.

Linking to Previous Case Studies

Analysis

10.47 In Space Text, an extra array was necessary to avoid the inefficiency of multiple insertions of blanks. Question 10.38 suggests that it is not necessary to use two arrays to shuffle a deck efficiently. Compare the two situations, and explain why efficient insertion into an array cannot be done without an extra array.

Modification

10.48 Modify the main program of Banners With CLASS to draw five random letters from P, Y, T, H, O and N. Each letter should have an equal chance of being chosen for the banner.

Modification

10.49 Modify the driver program of Space Text to generate a line containing a random number of randomly chosen words.

Application

10.50 Write a program that creates a history file for the You Are What You Eat program, using randomly chosen values for fat and calories.

Application

10.51 Describe two different ways to generate a random Roman numeral.

Reflection

10.52 Would randomly chosen test data have provided convincing evidence of the correctness of any of the programs in earlier case studies? In general, what kinds of programs would be best tested using random data?

Application

10.53 Describe two different ways to generate a random date in 1992.

Application

10.54 Write a program, modeled on the Banners With CLASS program, in which each of the letters A through Z corresponds to a particular randomly generated pattern stored in a two-dimensional array. The banner produced by the program would then be a combination of these patterns, a kind of computer art.

Reflection

10.55 List all variants of the "fill an array" template encountered so far in the case studies.

PerfectShuffle With Test Program

DECKSIZE = 10
NUMSHUFFLES = 20
CardType = 0
DeckType = [0 for _ in range(DECKSIZE)]
deck = DeckType.copy()
k = 0

""" Shuffle the deck as described in the commentary. """

def PerfectShuffle(deck):
oldPosition = 0
shuffledPosition = 0
shuffledDeck = DeckType.copy()
while oldPosition < DECKSIZE // 2:
shuffledDeck [shuffledPosition]
= deck[oldPosition]
oldPosition = oldPosition + 1
shuffledPosition = shuffledPosition + 2
shuffledPosition = 1
while oldPosition < DECKSIZE:
shuffledDeck [shuffledPosition]
= deck[oldPosition]
oldPosition = oldPosition + 1
shuffledPosition = shuffledPosition + 2
for oldPosition in range(DECKSIZE):
deck [oldPosition] = shuffledDeck [oldPosition]

""" Initialize the deck with 52 easily-identifiable elements for the purposes of testing. """

def Initialize(deck):
k = 0
for k in range(DECKSIZE):
deck[k] = k + 1
k = k -1

""" Print the deck (this procedure is for test purposes only) """

def Print(deck):
k = 0
print('Deck:')
for k in range(DECKSIZE):
print("{0:3d}".format(deck[k]), end = '')
print("\n")

# Main Program

Initialize(deck)
for k in range(NUMSHUFFLES):
PerfectShuffle(deck)
Print(deck)

SelectionShuffle and Accompanying Subprograms

DECKSIZE = 10
NUMSHUFFLES = 20
CardType = 0
DeckType = [0 for _ in range(DECKSIZE)]
deck = DeckType.copy()
k = 0

def Search(card, deck, deckSize):
k = 0
if deckSize == 0:
Search = False
else:
k = 0
while (k < deckSize) and (card != deck[k]):
k = k + 1
Search = (card == deck[k])
return Search

""" Return a randomly chosen deck position (a number between 1 and DECKSIZE, inclusive). """

def RandomDeckPos():
import random
RandomDeckPos = random. randint(0, DECKSIZE-1)
return RandomDeckPos

def SelectionShuffle(deck):
k = 0
numChosen = 0
shuffledDeck = DeckType.copy()
while numChosen < DECKSIZE:
k = RandomDeckPos()
if not Search(deck[k],
shuffledDeck, numChosen):
shuffledDeck [numChosen] = deck[k]
numChosen = numChosen + 1
for k in range(DECKSIZE):
deck[k] = shuffledDeck[k]

""" Initialize the deck with 10 easily-identifiable elements for the purposes of testing. """

def Initialize(deck):
k = 0
for k in range(DECKSIZE):
deck[k] = k + 1
k = k -1

""" Print the deck """

def Print(deck):
k = 0
print('Deck:')
for k in range(DECKSIZE):
print("{0:3d}".format(deck[k]), end = '')
print("\n")

# Main Program

Initialize(deck)
for k in range(NUMSHUFFLES):
SelectionShuffle(deck)
Print(deck)

Efficient SelectionShuffle and the Modified RandomDeckPos

DECKSIZE = 10
NUMSHUFFLES = 20
CardType = 0
DeckType = [0 for _ in range(DECKSIZE)]
deck = DeckType.copy()
k = 0

def RandomDeckPos(n):
import random
RandomDeckPos = random.randint(0, n-1)
return RandomDeckPos

def Efficient SelectionShuffle (deck):
k = 0
shuffledPos = 0
shuffledDeck = DeckType.copy()
for shuffledPos in range(DECKSIZE):
k = RandomDeckPos (DECKSIZE - shuffledPos)
shuffledDeck [shuffledPos] = deck[k]
deck[k] = deck[DECKSIZE -1 - shuffledPos]
for k in range(DECKSIZE):
deck[k] = shuffledDeck[k]

""" Initialize the deck with 10 easily-identifiable elements for the purposes of testing. """

def Initialize(deck):
k = 0
for k in range(DECKSIZE):
deck[k] = k + 1
k = k -1

""" Print the deck """

def Print(deck):
k = 0
print('Deck:')
for k in range(DECKSIZE):
print("{0:3d}".format(deck[k]), end = '')
print("\n")

# Main Program

Initialize(deck)
for k in range(NUMSHUFFLES):
Efficient SelectionShuffle (deck)
Print(deck)